РАЗМЕЩЕНИЕ С ИСПОЛЬЗОВАНИЕМ СВЯЗАННОГО СПИСКА
Метод заключается в представлении каждого файла в виде связанного списка дисковых блоков. Первое слово каждого блока используется в качестве указателя на следующий блок, а вся остальная часть блока предназначается для хранения данных.
РАЗМЕЩЕНИЕ С ИСПОЛЬЗОВАНИЕМ СВЯЗАННОГО СПИСКА
Потери дискового пространства на фрагментацию отсутствуют.
В то же время по сравнению с простотой последовательного чтения файла произвольный доступ является слишком медленным. Чтобы добраться до блока n, операционной системе нужно начать со стартовой позиции и прочитать поочередно n − 1 предшествующих блоков.
К тому же объем хранилища данных в блоках уже не кратен степени числа 2, поскольку несколько байтов отнимает указатель. Хотя это и не смертельно, но необычный размер менее эффективен, поскольку многие программы ведут чтение и запись блоками, размер которых кратен степени числа 2.
РАЗМЕЩЕНИЕ С ПОМОЩЬЮ СВЯЗАННОГО СПИСКА, ИСПОЛЬЗУЮЩЕГО ТАБЛИЦУ В ПАМЯТИ
Оба недостатка размещения с помощью связанных списков могут быть устранены за счет изъятия слова указателя из каждого дискового блока и помещения его в таблицу в памяти.
Используя таблицу, можно пройти всю цепочку от начального блока до самого конца. Цепочки заканчиваются специальным маркером (например, –1), который не является допустимым номером блока.
Такая таблица, находящаяся в оперативной памяти, называется FAT (File Allocation Table — таблица размещения файлов).
РАЗМЕЩЕНИЕ С ПОМОЩЬЮ СВЯЗАННОГО СПИСКА, ИСПОЛЬЗУЮЩЕГО ТАБЛИЦУ В ПАМЯТИ
При использовании такой организации для данных доступен весь блок.
Кроме того, намного упрощается произвольный доступ. Хотя для поиска заданного смещения в файле по-прежнему нужно идти по цепочке, эта цепочка целиком находится в памяти, поэтому проход по ней может осуществляться без обращений к диску.
Основным недостатком этого метода является то, что для его работы вся таблица должна постоянно находиться в памяти. Для 1- терабайтного диска, имеющего блоки размером 1 Кбайт, потребовалась бы таблица из 1 млрд записей, по одной для каждого из 1 млрд дисковых блоков. Каждая запись должна состоять как минимум из 3 байт. Для ускорения поиска размер записей должен быть увеличен до 4 байт. Таким образом, таблица будет постоянно занимать 3 Гбайт или 2,4 Гбайт оперативной памяти в зависимости от того, как оптимизирована система, под экономию пространства или под экономию времени, что с практической точки зрения выглядит не слишком привлекательно.
I-УЗЛЫ
Последним из рассматриваемых методов отслеживания принадлежности конкретного блока конкретному файлу является связь с каждым файлом структуры данных, называемой i-узлом (index-node — индекс-узел), содержащей атрибуты файла и дисковые адреса его блоков.
I-УЗЛЫ
При использовании i-узла появляется возможность найти все блоки файла. Большим преимуществом этой схемы является то, что i-узел должен быть в памяти только в том случае, когда открыт соответствующий файл.
Если каждый i-узел занимает n байт, а одновременно может быть открыто максимум k файлов, общий объем памяти, занимаемой массивом, хранящим i-узлы открытых файлов, составляет всего лишь kn байт.
I-УЗЛЫ
С i-узлами связана одна проблема: если каждый узел имеет пространство для фиксированного количества дисковых адресов, то что произойдет, когда файл перерастет этот лимит?
Одно из решений заключается в резервировании последнего дискового адреса не для блока данных, а для блока, содержащего дополнительные адреса блоков.
Может потребоваться даже дисковый блок, указывающий на другие, полные адресов дисковые блоки.
РЕАЛИЗАЦИЯ
КАТАЛОГОВ
Основной функцией системы каталогов является преобразование ASCII-имени файла в информацию, необходимую для определения местоположения данных.
Каждая файловая система работает с различными атрибутами файлов, такими как имя владельца файла и время создания, и их нужно где-то хранить.
РЕАЛИЗАЦИЯ
КАТАЛОГОВ
Одна из очевидных возможностей заключается в хранении их непосредственно в записи каталога. Именно так некоторые системы и делают.
В этой простой конструкции каталог состоит из списка записей фиксированного размера, по одной записи на каждый файл, в которой содержатся имя файла (фиксированной длины), структура атрибутов файла, а также один или несколько дисковых адресов (вплоть до некоторого максимума), сообщающих, где находятся соответствующие файлу блоки на диске.
РЕАЛИЗАЦИЯ
КАТАЛОГОВ
В MS-DOS у файлов имелось основное имя, состоящее из 1–8 символов, и необязательное расширение имени, состоящее из 1–3 символов. В UNIX версии 7 имена файлов состояли из 1–14 символов, включая любые расширения.
Но практически все современные ОС поддерживают длинные имена переменной длины. Как это может быть реализовано?
Проще всего установить предел длины имени файла (как правило, он составляет 255 символов) и отводить по 255 символов под каждое имя. Этот подход при всей своей простоте ведет к пустой трате пространства, занимаемого каталогом, поскольку такие длинные имена бывают далеко не у всех файлов.